import java.util.List;

//2.我的单链表
public class MySingleList implements IList{

    //静态内部类：定义节点
    static class ListNode{
        public int val;//节点的值
        public ListNode next;//下一个节点

        public ListNode(int val){//一个参数的构造方法，因为在构造的时候并不知道下一个节点是哪个在哪里，所以不初始化next
            this.val=val;
        }

    }
    /*静态内部类在实例化时要通过外部类：OuterClass.InnerClass innerClass=new OuterClass.InnerClass();*/

    public ListNode head;//当前链表的头结点
    public int listSize;//当前链表的长度

    //手动创建一个链表
    public void createList(){
        ListNode node1=new ListNode(12);
        ListNode node2=new ListNode(23);
        ListNode node3=new ListNode(34);
        ListNode node4=new ListNode(45);
        ListNode node5=new ListNode(56);

        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;

        this.head=node1;//因为node1一出这个方法就销毁了，所以要赋值给head
    }
    /*这样创建链表是一个非常low的操作，不建议这样创建，只是为了好理解才这样写*/

    //重写IList接口里的方法
    @Override
    //头插法
    public void addFirst(int data){
        ListNode node=new ListNode(data);//将要插入的这个数据变成一个节点
//        if(head==null){//说明链表没有元素，插入的这个节点就是头结点
//            this.head=node;
//        }else{//对于插入来说，一般建议先绑后面
//            node.next=this.head;
//            this.head=node;
//        }或者：
        //优化：（先完成再完美）
        node.next=this.head;//node.next=null
        this.head=node;
        this.listSize++;//别忘了链表长度要++
    }
    //尾插法
    @Override
    public void addLast(int data) {
        ListNode node=new ListNode(data);
        if(head==null){//链表为空
            //addFirst(data);或者：
            head=node;
            listSize++;
            return;
        }
        ListNode cur=this.head;
        while(cur.next!=null) {//当cur.next为空退出循环，cur.next为空说明现在的cur是最后一个节点了
            cur = cur.next;
        }
        cur.next=node;
        listSize++;
    }
    //任意位置插入
    @Override
    public void addIndex(int index, int data) throws  ListIndexOutOfBoundsException{//就分为三种情况嘛：只有后节点；只有前节点；前后都有节点
        checkIndexOfAdd(index);//一定要注意异常！特别面试的时候一定要写！
        if(index==0){
            addFirst(data);
        }else if(index==listSize){
            addLast(data);
        }else{
            ListNode node=new ListNode(data);
            ListNode cur=head;
            while(index-1!=0){//找到要插入位置的前一个节点cur
                cur=cur.next;
                index--;
            }
            node.next=cur.next;//还是一样，先绑后面
            cur.next=node;
            listSize++;
        }
    }
    private void checkIndexOfAdd(int index){//因为这个函数用户不直接使用，也不需要知道他的具体实现，所以设置为
        if(index<0||index>listSize){
            throw new ListIndexOutOfBoundsException("插入index位置不合法,index = "+index);
        }
    }
    //判断是否包含
    @Override
    public boolean contains(int key) {
        ListNode cur=head;
        while(cur!=null){//cur==null时，就已经遍历完了一整个链表了
            if(cur.val==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }
    //删除
    @Override
    public void remove(int key) {
        if(head==null){
            return;
        }
        if(head.val==key){
          head=head.next;
          listSize--;
          return;
        }
        ListNode cur=head;
        while(cur.next!=null){
            if(cur.next.val==key){//如果是while（cur!=null）那当cur为最后一个节点时，这段语句会出现空指针异常
                cur.next=cur.next.next;
                listSize--;
                return;
            }
            cur=cur.next;
        }
        System.out.println("没有您要删除的数据");
    }
    //删除
    @Override
    public void removeAllKey(int key) {
        if(head==null){
            return;
        }
//        if(head.val==key){
//            head=head.next;
//            listSize--;
//        }
//        ListNode cur=head;
//        while(cur.next!=null){
//            if(cur.next.val==key){//如果是while（cur!=null）那当cur为最后一个节点时，这段语句会出现空指针异常
//                cur.next=cur.next.next;
//                listSize--;
//            }
//            cur=cur.next;
//        }
//        if(cur.next==null){
//            return;
//        }
//        System.out.println("没有您要删除的数据");--删不了最后一个1
        /*while(head.val == key) {
            head = head.next;
        } 有可能会出现空指针异常*/
        ListNode cur=head.next;
        ListNode prev=head;
        while(cur!=null){
            if(cur.val==key){
                prev.next=cur.next;
                //cur=cur.next;
                listSize--;
            }else{
                prev=cur;
                //cur=cur.next;
            }
            cur=cur.next;
        }
        if(head.val==key){//这个为什么不放在ListNode cur=head.next;前，因为如果只有一个节点，且这个节点就是要删除的数据，那么会有空指针异常
            head=head.next;
            listSize--;
        }
    }
    //求长度
    @Override
    public int size() {
        return listSize;
    }
    //清除
    @Override
    public void clear() {
        head=null;//head置为空，所有的引用关系都消失了，链表空间就会被释放掉
        listSize=0;
    }
    //打印
    @Override
    public void display() {
        ListNode cur=head;
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }
    //从指定节点开始打印
    public void display(ListNode node){
        ListNode cur = node;
        while (cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
//        while(node!=null){
//            System.out.print(node.val+" ");
//            node=node.next;
//        }这样子改变了node
        System.out.println();
    }

    //给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
    public ListNode reverseList(ListNode head) {
        if(head==null){
            return null;
        }
        if(head.next==null){//只有一个节点
            return head;
        }
        ListNode cur=head.next;
        //1.ListNode curNext=cur.next;在这里定义，如果只有两个节点则空指针异常
        head.next=null;
        while(cur!=null){//如果是cur.next!=null 当执行到cur=curNext而curNext是最后一个节点时，此时cur.next为null退出了循环，最后一个节点并没有完成头插
            ListNode curNext=cur.next;
            cur.next=head;
            head=cur;
            cur=curNext;
            //1.curNext=curNext.next;
        }
        return head;
    }

    //找链表的中间节点，有两个中间节点返回第二个
    /*方法1*/
    public ListNode middleNode(){
        if(head==null){
            return head;
        }
        ListNode cur=head;
        int n=listSize/2;
        while(n!=0){
            cur=cur.next;
            n--;
        }
        return cur;
    }
    /*方法2：快慢指针*/
    public ListNode middleNode1(){
       if(head==null){
           return head;
       }
       ListNode fast=head;
       ListNode slow=head;
       while(fast!=null&&fast.next!=null){//当链表长度为偶数时的结束条件是fast==null，当链表长度为
                                          //奇数时，结束条件为fast.next==null，两个条件之间要用&&
                                          //不能用||，而且fast!=null在前，要先判断fast是不是等于null
                                          //要是先判断fast.next!=null那么当fast==null时会出现空指针异常
           fast=fast.next.next;
           slow=slow.next;
       }
       return slow;
    }

    //求倒数第k个节点
    public int kthToLast(int k) {
        if(k<=0||k>listSize){
            throw new ListIndexOutOfBoundsException("k的值不合法，k为"+k);//在这里可以返回-1也可以抛异常，但oj上不能抛异常，可能会被判错
        }
        ListNode fast=head;
        ListNode slow=head;
        while(k-1!=0){//fast先走k-1步
            fast=fast.next;
            k--;
        }
        //同时走
        while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow.val;
    }
    /*老师方法：
     public int kthToLast(int k) {
        if(k <= 0) {  //if(k <= 0 || k > len)
        return -1;
    }
    ListNode fast = head;
    ListNode slow = head;

    int count = 0;
    //
        while (count != k-1) {
        fast = fast.next;
        if(fast == null) {
            return -1;
        }
        count++;
    }
    //同时走
        while (fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
        return slow.val;
}*/

    //给定值x为基准将链表分割成两部分
    public ListNode partition(int x) {
        ListNode cur = head;
        ListNode bs = null;//before start
        ListNode be = null;//before end
        ListNode as = null;//after start
        ListNode ae = null;//after end
        while (cur != null) {//循环结束时cur走完整个链表
            if (cur.val < x) {//<x  放前面
                if (bs == null) {//判断是不是第一次插入
                    bs = be = cur;
                } else {//对bs进行尾插
                    be.next = cur;
                    be = cur;
                }
            } else {//>x  放后面
                if (as == null) {//判断是不是第一次插入
                    as = ae = cur;
                } else {
                    ae.next = cur;
                    ae = cur;
                }
            }
            cur = cur.next;
        }
        if (bs == null) { //前面没有
            // ae.next=null;//最后一个节点的后驱手动置空 //”相对位置不变“ 所以ae的next一定为空
            return as;
        }
        be.next = as;//把两部分连接起来
        /*if(as==null){//后面没有
            be.next=null;//最后一个节点的后驱手动置空 //”相对位置不变“ 所以be的next一定为空
            return bs;
        }这种情况不需要讨论 因为这种情况不特殊 上面的代码 be.next=as;下面的代码return bs;包含了这里面的if内容*/
        if (as != null) {
            ae.next = null;//手动置空
        }
        return bs;
    }


    //判断链表是不是回文链表
    public boolean chkPalindrome() {
        if(head==null){
            return false;
        }
        if(head.next==null){//只有一个节点
            return true;
        }

        //找中间节点
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }

        //反转一半的链表
        ListNode cur=slow.next;
        //ListNode curNext=cur.next;在这里定义，如果只有两个节点则空指针异常
        //不用将slow.next置为空
        //进行头插
        while(cur!=null){//而不是cur.next!=null
            ListNode curNext=cur.next;
            cur.next=slow;
            slow=cur;
            cur=curNext;
        }

        //head从头走，slow从尾走
        while(head!=slow){//相遇退出循环
            if(head.val!=slow.val){
                return false;
            }
            if(head.next==slow){//判断偶数情况
                return true;
            }
            head=head.next;
            slow=slow.next;
        }
        return true;
    }



    //求两个链表第一个共同节点
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // if(headA==null||headB==null){
        //     return null;
        // }这个在后面的代码中都包含了，就算

        //求A、B长度
        ListNode cur1=headA;
        ListNode cur2=headB;
        int len1=0;
        int len2=0;
        while(cur1!=null){
            len1++;
            cur1=cur1.next;
        }
        while(cur2!=null){
            len2++;
            cur2=cur2.next;
        }

        //求A、B长度差 长链表先走len步
        int len=len1-len2;
        if(len<0){//让headA所指向的那个链表为长链表
            ListNode tmp=headB;
            headB=headA;
            headA=tmp;
            len=(-1)*len;
        }
        while(len!=0){//走len步
            headA=headA.next;
            len--;
        }

        //一起走直到相交
        while(headA!=null||headB!=null){
            if(headA==headB){
                return headA;
            }
            headA=headA.next;
            headB=headB.next;
        }
        return null;
    }
    /*老师的代码：*/
//    public static MySingleList.ListNode getIntersectionNode(MySingleList.ListNode headA,
//                                                            MySingleList.ListNode headB) {
//        //1. 假定 A链表长  B链表短
//        MySingleList.ListNode pl = headA;
//        MySingleList.ListNode ps = headB;
//
//        //2.分别求两个链表的长度
//
//        int len1 = 0;
//        int len2 = 0;
//        while (pl != null) {
//            len1++;
//            pl = pl.next;
//        }
//
//        while (ps != null) {
//            len2++;
//            ps = ps.next;
//        }
//        pl = headA;
//        ps = headB;
//
//        //3. 求长度的差值 len
//
//        //len < 0   -->  pl = headB  ps = headA len = len2 - len1
//        int len = len1 - len2;
//        if(len < 0) {
//            pl = headB;
//            ps = headA;
//            len = len2 - len1;
//        }
//        //4. 确定 pl指向的链表 一定是长 链表   ps指向的节点 一定是短链表
//
//        //5.让pl走 len步
//        while (len != 0) {
//            pl = pl.next;
//            len--;
//        }
//
//        //6. ps 和 pl 同时走 直到相遇
//        while (pl != ps) {
//            pl = pl.next;
//            ps = ps.next;
//        }
//
//        //如果没有相遇 那么pl == null
//        if(pl == null) {
//            return null;
//        }
//        return pl;
//    }


    //判断是否带环
    public boolean hasCycle() {
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                return true;
            }
        }
        return false;
    }

    //返回链表开始入环的第一个节点
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                break;
            }
        }
        if(fast == null || fast.next == null) {
            return null;//没有环 就没有入口点
        }

        fast = head;
        while(fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}
